// class Solution {
//     public:
//         int row[9][10] = {0};
//         int col[9][10] = {0};
//         int mboard[3][3][10]={0};
//         void solveSudoku(vector<vector<char>>& board) {
//             for(int i = 0 ; i < 9 ; i++){
//                 for(int j = 0 ; j < 9 ; j++){
//                     if(board[i][j] != '.'){
//                         int g = board[i][j]-'0';
//                         row[i][g] =1;col[j][g] =1; mboard[i/3][j/3][g]=1;
//                     }
//                 }
//             }
//             dfs(board,0,0);
//             return;
//         }
//         bool found = false;
//         void dfs(vector<vector<char>>& board,int i,int j ){
//             if(found)   return;
//             if( i == 9 ){
//                 found = true;
//                 return;
//             }
//             if( j == 9 ){
//                 dfs(board,i+1,0);
//                 return;
//             }
//             if(board[i][j] !='.'){
//                 dfs(board,i,j+1);
//                 return;
//             }
//             for(int g = 1 ; g <= 9 ; g++){
//                 if(row[i][g] == 0&&col[j][g] == 0 && mboard[i/3][j/3][g] == 0){
//                     board[i][j] = g+'0';
//                     row[i][g] = 1;col[j][g] =1;mboard[i/3][j/3][g] =1;
//                     dfs(board,i,j+1);
//                     if(found) return;board[i][j] ='.';
//                     row[i][g] = 0;col[j][g] =0;mboard[i/3][j/3][g] =0;
//                 }
//             }
//         }
    
//     };

class Solution {
    public:
        int row[9][10] = {0};
        int col[9][10] = {0};
        int mboard[3][3][10]={0};
        void solveSudoku(vector<vector<char>>& board) {
            for(int i = 0 ; i < 9 ; i++){
                for(int j = 0 ; j < 9 ; j++){
                    if(board[i][j] != '.'){
                        int g = board[i][j]-'0';
                        row[i][g] =1;col[j][g] =1; mboard[i/3][j/3][g]=1;
                    }
                }
            }
            dfs(board,0);
            return;
        }
        bool found = false;
        void dfs(vector<vector<char>>& board,int cnt){
            if(cnt == 81){
                found = true;
                return;
            }
            int x = cnt / 9;
            int y = cnt % 9;
            if(board[x][y] != '.'){
                dfs(board,cnt+1); //进入下一层
                return;
            }else{
                for(int i = 1 ; i <= 9 ; i++){
                    if(row[x][i] == 0 && col[y][i] == 0 && mboard[x/3][y/3][i] == 0){
                        board[x][y] = i+'0';
                        row[x][i] = col[y][i] = mboard[x/3][y/3][i] = 1;
                        dfs(board,cnt+1);
                        if(found) return;
                        board[x][y] = '.';
                        row[x][i] = col[y][i] = mboard[x/3][y/3][i] = 0;
                    }
                }
            }
        }
    
    };